package _02array;

public class _06InsertSortArray {

    public static void main(String[] args) {

        int[] arr = new int[20];
        int[] arrBase = {1, 4, 7, 10, 15, 19, 22, 30, 31};

        int capacity = arrBase.length;
        int endIndex = 8;
        System.arraycopy(arrBase, 0, arr, 0, capacity );


        // insert 20
        int target = 20;
        capacity = arr.length;
        endIndex = insertSorted(arr, endIndex, target, capacity);

        for(int i = 0; i <= endIndex; i++)
            System.out.print(" " + arr[i]);

        System.out.println();
    }

    // insert target
    // time complexity: O(n)
    // space complexity: O(1)
    private static int insertSorted(int arr[], int index, int target, int capacity) {

        // more than or equal to capacity
        if (index >= capacity - 1) {
            return index;
        }
        // move
        int i;
        for (i = index; i >= 0 && arr[i] > target; i--)
            arr[i + 1] = arr[i];

        // insert
        arr[i + 1] = target;

        return index + 1;
    }
}
